package com.skh.string;

/**
 * @Author: skh
 * @Date: 2020/3/19 10:03
 * @Description: 最长回文串
 */
public class LongestPalindrome {
    /**
     * 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
     *
     * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
     *
     * 注意:
     * 假设字符串的长度不会超过 1010。
     *
     * 示例 1:
     *
     * 输入:
     * "abccccdd"
     *
     * 输出:
     * 7
     *
     * 解释:
     * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
     */

    /**
     * 思路1
     * 用哈希表统计每个字符出现的次数
     * 判断奇偶性：
     * 若字符出现次数为偶数，则肯定能够组成回文串，计入累加器
     * 若为奇数，添加个数-1并计入累加器，并且标记存在中心字符
     * @param s
     * @returnreverseList
     */
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        for (int c : s.toCharArray()) {
            count[c]++;
        }

        int center = 0;
        int sum = 0;
        for (int i : count) {
            if (i % 2 == 0) {
                sum+=i;
            }else {
                sum+=i-1;
                center=1;
            }
        }

        return sum+center;
    }
}
